package com.hspedu.newData.dmsxl.树.构造二叉树;

import com.hspedu.newData.dmsxl.ds.TreeNode;
import org.junit.Test;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * @Author: yh
 * @description: 
 * @CreateTime: 2025-05-21 
 * @Version: 1.0
 */

public class LC1008前序遍历构造二叉搜索树 {

    // todo 效率不高
    Map<Integer,Integer> map = new HashMap<>();

    public TreeNode bstFromPreorder(int[] preorder) {

        int[] inorder = Arrays.copyOf(preorder,preorder.length);
        Arrays.sort(inorder);
        if (preorder.length == 0){
            return null;
        }
        for (int i = 0; i < preorder.length; i++) {
            map.put(inorder[i],i);
        }

        TreeNode root = dfs(preorder,0,preorder.length,inorder,0,preorder.length);
        return root;

    }

    public TreeNode dfs(int[] preorder,int pStart,int pEnd,int[] inorder,int iStart,int iEnd){
        if (pStart>=pEnd || iStart>=iEnd){
            return null;
        }

        int index = map.get(preorder[pStart]);
        int lenLeft = index - iStart;

        TreeNode root = new TreeNode(inorder[index]);

        root.left = dfs(preorder,pStart+1,pStart + 1+lenLeft,inorder,iStart,index);
        root.right = dfs(preorder,pStart+1+lenLeft,pEnd,inorder,index+1,iEnd);

        return root;
    }

    @Test
    public void test() {
        // 测试代码
        bstFromPreorder(new int[]{8,5,1,7,10,12});
    }

}
